﻿namespace 贪心算法示例
{
    // 聚会类：存储聚会名称和时间
    public class Meeting
    {
        public string Name { get; set; }       // 聚会名称
        public int StartTime { get; set; }    // 开始时间（简化为整数，如9表示9点）
        public int EndTime { get; set; }      // 结束时间（如10表示10点）

        public Meeting(string name, int startTime, int endTime)
        {
            Name = name;
            StartTime = startTime;
            EndTime = endTime;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // 1. 定义所有可选的聚会（时间可能冲突）
            var meetings = new List<Meeting>
        {
            new Meeting("聚会A", 9, 10),    // 9:00-10:00
            new Meeting("聚会B", 9, 11),    // 9:30-11:00（简化为9-11）
            new Meeting("聚会C", 10, 12),   // 10:30-12:00（简化为10-12）
            new Meeting("聚会D", 11, 13),   // 11:00-13:00
            new Meeting("聚会E", 14, 15)    // 14:00-15:00
        };

            // 2. 应用贪心算法选择最多不冲突的聚会
            var selectedMeetings = SelectMaxMeetings(meetings);

            // 3. 输出结果
            Console.WriteLine("最多可参加的聚会（不冲突）：");
            foreach (var meeting in selectedMeetings)
            {
                Console.WriteLine($"- {meeting.Name}：{meeting.StartTime}:00-{meeting.EndTime}:00");
            }
        }

        /// <summary>
        /// 贪心算法核心：选择最多不冲突的聚会
        /// 策略：每次选择结束时间最早的聚会，为后续留出更多时间
        /// </summary>
        /// <param name="meetings">所有聚会列表</param>
        /// <returns>选中的聚会列表</returns>
        static List<Meeting> SelectMaxMeetings(List<Meeting> meetings)
        {
            // 步骤1：按结束时间升序排序（贪心策略的关键）
            var sortedMeetings = meetings.OrderBy(m => m.EndTime).ToList();

            // 步骤2：筛选不冲突的聚会
            var selected = new List<Meeting>();
            int lastEndTime = -1;  // 记录上一个选中聚会的结束时间（初始化为负数，确保第一个聚会能被选中）

            foreach (var meeting in sortedMeetings)
            {
                // 如果当前聚会的开始时间 >= 上一个聚会的结束时间，说明不冲突
                if (meeting.StartTime >= lastEndTime)
                {
                    selected.Add(meeting);
                    lastEndTime = meeting.EndTime;  // 更新最后结束时间
                }
            }

            return selected;
        }
    }



}
